package com.排序.排序基础;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class 桶排序 {
    public static void sort(int[] a,int range) {
        int max = a[0];
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
            if (a[i] < min) {
                min = a[i];
            }
        }

        ArrayList<Integer>[] buckets = (ArrayList<Integer>[]) new ArrayList[(max - min) / range + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        for(int age : a){
            buckets[(age - min )/range].add(age);
        }
        int k = 0;
        for(ArrayList<Integer> bucket : buckets){
           Collections.sort(bucket);
        }

        for (ArrayList<Integer> bucket : buckets) {
            for (int num : bucket) {
                a[k++] = num;
            }
        }
    }
}
